package org.laizili.solution.nowcodertop101.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=295&sfm=html&channel=nowcoder">BM77. 最长括号子串</a>
 * <p>
 *     tags: 栈; 动态规划
 * </p>
 * <p>
 *     notes:
 *       1. 栈状态维护，最值更新
 *       2. TODO: 动态规划解法
 *
 * </p>
 */
public class BM77 {
    public static class Solution {
        /**
         * @param s string字符串
         * @return int整型
         */
        public int longestValidParentheses(String s) {
            // write code here
            Deque<Integer> stack = new ArrayDeque<>();
            int res = 0;
            char[] charArray = s.toCharArray();
            int lastDisMathPos = -1;
            for (int i = 0; i < charArray.length; i++) {
                int ch = charArray[i];
                if (ch == ')') {
                    if (stack.isEmpty()) {
                        lastDisMathPos = i;
                    } else {
                        stack.pop();
                        res = stack.isEmpty() ? Math.max(res, i - lastDisMathPos) : Math.max(res, i - stack.peek());
                    }
                } else {
                    // '('
                    stack.push(i);
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().longestValidParentheses("())"));
    }
}
